#
# @lc app=leetcode.cn id=42 lang=python3
#
# [42] 接雨水
#

"""
本题与11题类似，容器能盛多少水，取决于较短的柱子边
所以本题的思路是使用前后缀的方式，从两边开始分别记录最高的柱子高度
那么某个位置的接水量等于当前位置的前后缀的最小值减去当前位置的高度
"""


# @lc code=start
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        
        pre_max = [0] * n
        pre_max[0] = height[0]
        for i in range(1, n):
            pre_max[i] = max(pre_max[i-1], height[i])
            
        suf_max = [0] * n
        suf_max[-1] = height[-1]
        for i in range(n-2, -1, -1):
            suf_max[i] = max(suf_max[i+1], height[i])
            
        res = 0
        for i in range(n-1):
            res += min(pre_max[i], suf_max[i]) - height[i]
            
        return res
        
# @lc code=end

